package lc_1072_按列翻转得到最大值等行数;

import java.util.HashMap;
import java.util.Map;

//https://leetcode.cn/problems/flip-columns-for-maximum-number-of-equal-rows/
public class Solution_哈希表 {
	
	//执行用时：8 ms, 在所有 Java 提交中击败了92.59%的用户
	//
	//内存消耗：58.7 MB, 在所有 Java 提交中击败了5.56%的用户
	//
	//通过测试用例：89 / 89
	public int maxEqualRowsAfterFlips1(int[][] matrix) {
		int n = matrix[0].length;
		Map<String, Integer> cnts = new HashMap<>();
		int ans = 0;
		for (int[] row : matrix) {
			char[] cs = new char[n];
			for (int i = 0; i < n; i++) {
				cs[i] = (char) (row[i] ^ row[0]);
			}
			String str = new String(cs);
			cnts.put(str, cnts.getOrDefault(str, 0) + 1);
			ans = Math.max(cnts.get(str), ans);
		}
		return ans;
	}
	
	//	执行用时：14 ms, 在所有 Java 提交中击败了78.70%的用户
	//
	//	内存消耗：54.7 MB, 在所有 Java 提交中击败了33.33%的用户
	//
	//	通过测试用例：89 / 89
	public int maxEqualRowsAfterFlips2(int[][] matrix) {
		int n = matrix[0].length;
		Map<String, Integer> cnts = new HashMap<>();
		int ans = 0;
		for (int[] row : matrix) {
			char[] cs = new char[n];
			for (int i = 0; i < n; i++) {
				cs[i] = (char) (row[i] ^ row[0]);
			}
			cnts.put(new String(cs), cnts.getOrDefault(new String(cs), 0) + 1);
			ans = Math.max(cnts.get(new String(cs)), ans);
		}
		return ans;
	}
	//	执行用时：8 ms, 在所有 Java 提交中击败了92.59%的用户
	//
	//	内存消耗：58.3 MB, 在所有 Java 提交中击败了7.41%的用户
	//
	//	通过测试用例：89 / 89
	public int maxEqualRowsAfterFlips3(int[][] matrix) {
		int n = matrix[0].length;
		Map<String, Integer> cnts = new HashMap<>();
		int ans = 0;
		for (int[] row : matrix) {
			char[] cs = new char[n];
			for (int i = 0; i < n; i++) {
				cs[i] = (char) (row[i] ^ row[0]);
			}
			String str = new String(cs);
			cnts.merge(str, 1, Integer::sum);
			ans = Math.max(cnts.get(str), ans);
		}
		return ans;
	}
	
	//	执行用时：7 ms, 在所有 Java 提交中击败了94.44%的用户
	//
	//	内存消耗：57.2 MB, 在所有 Java 提交中击败了8.34%的用户
	//
	//	通过测试用例：89 / 89
	public int maxEqualRowsAfterFlips4(int[][] matrix) {
		int n = matrix[0].length;
		Map<String, Integer> cnts = new HashMap<>();
		int ans = 0;
		for (int[] row : matrix) {
			char[] cs = new char[n];
			for (int i = 0; i < n; i++) {
				cs[i] = (char) (row[i] ^ row[0]);
			}
			String str = new String(cs);
			int c = cnts.merge(str, 1, Integer::sum);
			ans = Math.max(c, ans);
		}
		return ans;
	}
	
	//	执行用时：7 ms, 在所有 Java 提交中击败了94.44%的用户
	//
	//	内存消耗：58.1 MB, 在所有 Java 提交中击败了7.41%的用户
	//
	//	通过测试用例：89 / 89
	public int maxEqualRowsAfterFlips5(int[][] matrix) {
		int n = matrix[0].length;
		Map<String, Integer> cnts = new HashMap<>();
		int ans = 0;
		for (int[] row : matrix) {
			char[] cs = new char[n];
			for (int i = 0; i < n; i++) {
				cs[i] = (char) (row[i] ^ row[0]);
			}
			int c = cnts.merge(new String(cs), 1, Integer::sum);
			ans = Math.max(c, ans);
		}
		return ans;
	}
	
	
	//	执行用时：39 ms, 在所有 Java 提交中击败了34.26%的用户
	//
	//	内存消耗：57 MB, 在所有 Java 提交中击败了9.26%的用户
	//
	//	通过测试用例：89 / 89
	public int maxEqualRowsAfterFlips(int[][] matrix) {
		int n = matrix[0].length;
		Map<String, Integer> cnts = new HashMap<>();
		int ans = 0;
		for (int[] row : matrix) {
			StringBuffer sb = new StringBuffer();
			for (int i = 0; i < n; i++) {
				sb.append(row[i] ^ row[0]);
			}
			int c = cnts.merge(sb.toString(), 1, Integer::sum);
			ans = Math.max(c, ans);
		}
		return ans;
	}
}